package com.xsherl.leetcode.solution;

import com.xsherl.leetcode.utils.PrintUtils;

import java.util.Arrays;

public class ScrambleString {

    /**
     * 动态规划
     * 要判断s1和s2能否混淆，就需要判断两个字符的子串s1[i:j]和s2[x:y]能否混淆
     * 存储s1[i:j]和s2[x:y]能否混淆的结果，需要一个四位数组，dp[i][j][x][y];
     * 又因为两个子串长度相等，所以可以等价为 dp[i][x][len]
     *
     *  dp[i][x][len] = {
     *      dp[i][x][k] && dp[i + k][x + k][len - k]
     *      || dp[i][x + (len - k)][k] && dp[i + (len - k)][x][len - k]
     *  }
     *
     * @param s1,s2 s1.length == s2.length
     *              1 <= s1.length <= 30
     *              s1 和 s2 由小写英文字母组成
     */
    public boolean isScramble(String s1, String s2) {
        int len = s1.length();
        boolean[][][] dp = new boolean[len][len][len + 1];
        for (int i = 0; i < len; ++i){
            for (int x = 0; x < len; ++x){
                dp[i][x][0] = true;
                if (s1.charAt(i) == s2.charAt(x)){
                    dp[i][x][1] = true;
                }
            }
        }
        for (int L = 2; L <= len; L++) {
            for (int i = 0; i <= len - L; ++i){
                for (int x = 0; x <= len - L; ++x){
                    for (int k = 1; k < L; ++k) {
                        boolean flag1 = dp[i][x][k] && dp[i + k][x + k][L - k];
                        if (flag1){
                            dp[i][x][L] = true;
                            break;
                        }
                        boolean flag2 = dp[i][x + (L - k)][k] && dp[i + k][x][L - k];
                        if (flag2){
                            dp[i][x][L] = true;
                            break;
                        }
                    }
                }
            }
        }
        return dp[0][0][len - 1];
    }

    /**
     * 递归
     */
    public boolean isScramble1(String s1, String s2) {
        if (s1.length() != s2.length()){
            return false;
        }
        if (s1.equals(s2)) {
            return true;
        }
        int len = s1.length();
        if (len <= 1){
            return false;
        }
        for (int i = 1; i < len; ++i){
            boolean flag1 = isScramble1(s1.substring(0, i), s2.substring(0, i))
                    && isScramble1(s1.substring(i, len), s2.substring(i, len));
            boolean flag2 = isScramble1(s1.substring(0, i), s2.substring(len - i, len))
                    && isScramble1(s1.substring(i, len), s2.substring(0, len - i));
            boolean flag = flag1 || flag2;
            if (flag){
                return true;
            }
        }
        return false;
    }

    /**
     * 递归 + 记忆搜索
     */
    private String s1;
    private String s2;
    private int[][][] cache;
    public boolean isScramble2(String s1, String s2) {
        this.s1 = s1;
        this.s2 = s2;
        int len = s1.length();
        cache = new int[len][len][len + 1];
        return dfs(0, 0, len);
    }

    private boolean dfs(int i, int j, int len){
        if (cache[i][j][len] != 0){
            return cache[i][j][len] == 1;
        }
        if (s1.substring(i, i + len).equals(s2.substring(j, j + len))) {
            cache[i][j][len] = 1;
            return true;
        }
        if (len <= 1){
            cache[i][j][len] = -1;
            return false;
        }
        for (int k = 1; k < len; ++k){
            if (dfs(i, j, k) && dfs(i + k, j + k, len - k)){
                cache[i][j][len] = 1;
                return true;
            }
            if (dfs(i, j + (len - k), k) && dfs(i + k, j, len - k)){
                cache[i][j][len] = 1;
                return true;
            }
        }
        cache[i][j][len] = -1;
        return false;
    }

    public static void main(String[] args) {
        String s1 = "great";
        String s2 = "rgeat";
        boolean scramble = new ScrambleString().isScramble2(s1, s2);
        System.out.println(scramble);
    }

}
